package com.interview.javabase.algorithm.链表;

public class 两数相加 {

    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(9);
        listNode1.next = new ListNode(9);
        listNode1.next.next = new ListNode(9);


        ListNode listNode2 = new ListNode(9);
        listNode2.next = new ListNode(9);
        listNode2.next.next = new ListNode(9);

        ListNode add = add(listNode1, listNode2);
        while (add != null) {
            System.out.println(add.val);
            add = add.next;
        }

    }

    private static ListNode add(ListNode l1, ListNode l2) {

        ListNode newHead = new ListNode(0);
        ListNode newTail = newHead;

        ListNode temp1 = l1;
        ListNode temp2 = l2;

        int i = 0;
        while (temp1 != null || temp2 != null) {
            int sum = 0;

            if (temp1 != null) {
                sum += temp1.val;
                temp1 = temp1.next;
            }

            if (temp2 != null) {
                sum += temp2.val;
                temp2 = temp2.next;
            }

            sum += i;
            if (sum >= 10) {

                ListNode listNode = new ListNode(sum % 10);
                newTail.next = listNode;
                newTail = listNode;
                i = sum / 10;
            } else {
                ListNode listNode = new ListNode(sum);
                newTail.next = listNode;
                newTail = listNode;
            }
        }

        if (i > 0) {
            newTail.next =  new ListNode(i);
        }

        return newHead.next;
    }
}
